package DataStructure.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 18. 四数之和 https://leetcode.cn/problems/4sum/
 * 题目简述：找出一个数组中所有四个不同位置和为target的不重复的四元组
 */
public class FourSum {

    public static void main(String[] args) {
        new FourSum().fourSum(new int[]{1000000000,1000000000,1000000000,1000000000}, -294967296);
    }

    /**
     * 思路：在三数之和的基础上再套一层指针就行了。需要注意的一个点是，此题设的数据范围为10^9，而int类型的数据范围是[-2^31, 2^31-1]，即正负21亿多，故加和可能会出现精度溢出问题，计算加和前需先转为long类型
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        //先排好序
        Arrays.sort(nums);
        //然后从左向右每遍历一个元素a，指针b,c,d使用三数之和的方法扫描[a+1, len-1]，寻找所有包含a的四数之和为target的四元组
        for(int a = 0;a < nums.length;a++) {
            //若nums[a]已经大于target并且nums[a] > 0，则后面的元素都已经大于0了，加上去四数之和肯定大于target，直接退出循环
            if(nums[a] > target && nums[a] > 0) break;
            //重复的a元素得出的四元组肯定是一样的，直接过滤掉
            if(a > 0 && nums[a] == nums[a-1]) continue;
            //使用三数之和的方法扫描[a+1, len-1]
            for(int b = a+1;b < nums.length;b++) {
                //若nums[a] + nums[b]已经大于target并且nums[b] > 0，则后面的元素都已经大于0了，加上去四数之和肯定大于target，故退出循环
                if (nums[a] + nums[b] > target && nums[b] > 0) break;
                if(b > a+1 && nums[b] == nums[b-1]) continue;
                int c = b + 1;
                int d = nums.length - 1;
                while(c < d) {
                    //只需要将第一个数nums[a]转成long类型就行了
                    long sum = (long)nums[a] + nums[b] + nums[c] + nums[d];
                    if(sum == target) {
                        result.add(Arrays.asList(nums[a], nums[b], nums[c], nums[d]));
                        c++;
                        while(c < d && nums[c] == nums[c-1]) {
                            c++;
                        }
                        d--;
                        while(c < d && nums[d] == nums[d+1]) {
                            d--;
                        }
                    } else if(sum < target) {
                        c++;
                    } else {
                        d--;
                    }
                }
            }
        }
        return result;
    }
}
